//
// Created by Semir on 2020/4/19.
//

#include <iostream>
#include <vector>

using namespace std;

struct Goods {
    int cost;
    int score;
};

Goods* CreateGoods(int cost, int score) {
    Goods* goods = new Goods;
    goods->cost = cost;
    goods->score = score;
    return goods;
}

const int MAX_N = 60;
int money, n;
vector<vector<Goods*> > p;
vector<int> dp;

int main() {
    cin >> money >> n;
    money /= 10;
    p.resize(n + 1);
    dp.resize(money + 1);
    int tempCost, tempDegree, tempGroup;
    for (int i = 1; i <= n; i++) {
        cin >> tempCost >> tempDegree >> tempGroup;
        tempCost /= 10;
        if (tempGroup == 0) {
//            p[i].insert(p[i].begin(), 1, CreateGoods(tempCost, tempDegree * tempCost))
            p[i].resize(1);
            p[i][0] = CreateGoods(tempCost, tempDegree * tempCost);
        } else if (p[tempGroup].size() == 1) {
            p[tempGroup].resize(2);
            p[tempGroup][1] = CreateGoods(tempCost + p[tempGroup][0]->cost,
                    tempDegree * tempCost + p[tempGroup][0]->score);
        } else {
            p[tempGroup].resize(4);
            p[tempGroup][2] = CreateGoods(tempCost + p[tempGroup][0]->cost,
                                          tempDegree * tempCost + p[tempGroup][0]->score);
            p[tempGroup][3] = CreateGoods(p[tempGroup][1]->cost + tempCost,
                     tempDegree * tempCost + p[tempGroup][1]->score);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (p[i].empty()) {
            continue;
        }
        for (int j = money; j >= 0; j--) {
            for (int k = 0; k < p[i].size(); k++) {
                if (j >= p[i][k]->cost) {
                    dp[j] = max(dp[j], dp[j - p[i][k]->cost] + p[i][k]->score);
                }
            }
        }
    }
    cout << dp[money] * 10 << endl;
    return 0;
}